

#include"tree.h"
#include"utility.h"
#include<stdio.h>
#include<stdlib.h>

TreeNode * TreeNode_create(char val,int freq){

    TreeNode * tn = (TreeNode*)malloc(sizeof(TreeNode));
    // 做判断 以防malloc失败
    if (NULL == tn)
    {
        printf("malloc sizeof(TreeNode) failed.\n");
        return NULL;
    }
    tn->value = val;
    tn->freq = freq;
    tn->left = NULL;
    tn->right = NULL;

    return tn;
}

TreeNode * TreeNode_merge(TreeNode * tn1,TreeNode * tn2){

    TreeNode * tn = TreeNode_create('0',tn1->freq + tn2->freq);
    if(NULL ==  tn){

        return NULL;
    }
    // 这里一般的是t1->freq <= tn2->freq
    tn->left = tn1;
    tn->right = tn2;
    return tn;
}
// 后序
void Tree_print(TreeNode * tn,int level){

    if(NULL == tn)
    {

        return;
    }
    Tree_print(tn->left,level + 1);
    Tree_print(tn->right,level + 1);

    int depth = 0;
    if(;depth < level;depth++)
    {

        printf("    ");
    }
    printf("freq = %d ",tn->freq);
    if(NULL == tn->left && NULL == tn->right)
    {

        printf("value = %d, '%c'",tn->freq,tn->value);
    }
    printf("\n");
}

static int Tree_heightHelper(TreeNode * tn,int height){

    if(NULL == tn){

        return height;
    }
    TreeNode * leftc = tn->left;
    TreeNode * rightc = tn->right;

    int lh = Tree_heightHelper(leftc,height+1); 
    int rh = Tree_heightHelper(rightc,height+1); 

    if(lh > rh){

        return lh;
    }
    return rh;
}

int Tree_height(TreeNode * tn){

    int height = 0;
    height = Tree_heightHelper(tn,0);
    
    return height;
}

static void Tree_leafHelper(TreeNode * tn,int * num){

    if(NULL == tn){

        return;
    }
    if(NULL == tn->left && NULL == tn->right){

        (*num)++;
        // return;
    }
    // 不做判断也可以直接调用
    if(NULL != tn->left){

        Tree_leafHelper(tn->left,num);
    }
    if(NULL != tn->right){

        Tree_leafHelper(tn->right,num);
    }
}

int Tree_leaf(TreeNode * tn){

    int num = 0;
    Tree_leafHelper(tn,&num);

    return num;
}

static void char2Bits(FILE * outfptr,int ch,unsigned char * whichbit,unsigned char * curbyte){

    unsigned char mask = 0x40;  // 只有7位 64
    while(mask > 0){

        // ch belong to [0,127] 也只有7位有效位
        // 即将字符的二进制编码加入到curbye当中
        writeBit(outfptr,(ch & mask) == mask,whichbit,curbyte);
        mask  = mask >> 1;
    }
}

static void Tree_headerHelper(TreeNode * tn,FILE * outfptr,unsigned char * whichbit,unsigned char * curbyte){

    if(NULL == tn){

        return;
    }
    TreeNode * lc = tn->left;
    TreeNode * rc = tn->right;
    if(lc == NULL && rc == NULL){

        writeBit(outfptr,1,whichbit,curbyte);
        char2Bits(outfptr,tn->value,whichbit,curbyte);
        return;
    }
    Tree_headerHelper(lc,outfptr,whichbit,curbyte);
    Tree_headerHelper(rc,outfptr,whichbit,curbyte);
    // 非叶子节点（是需要产生位移的）（在生产的头部编码中每出现一个非叶子节点就产生一个0位）所以有了位移
    writeBit(outfptr,0,whichbit,curbyte);
}


void Tree_header(TreeNode * tn,unsigned int numChar,char * outfile){

    FILE * outfptr = fopen(outfile,"w");
    if(NULL == outfptr){

        printf("%s %d open file failed.\n",__FILE__,__LINE__);
        return;
    }
    //
    unsigned char whichbit = 0;
    unsigned char curbyte = 0;
    Tree_headerHelper(tn,outfptr,&whichbit,&curbyte);
    // 在头文件末尾多加入一个0（这里也可能产生位移）
    writeBit(outfptr,0,&whichbit,&curbyte);
    // 
    padZero(outfptr,&whichbit,&curbyte);

    // 写入字符的数目（4个字节）
    fwrite(&numChar,sizeof(unsigned int),1,outfptr);
    // 添加'\n'在头文件的末尾
    unsigned char newline = '\n';
    fwrite(&newline,sizeof(unsigned char),1,outfptr);
    fclose(outfptr);
}
